#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <limits.h>
#include "logger2.h"

#define INFO 0
#define WARN 1
#define ERROR 2

int max_size_of_int = 10;
int exact_num_of_parts;
//size of input file.

off_t size_of_file(char *INPUT){
    struct stat st;
    stat(INPUT, &st);
    off_t size = st.st_size;
    return size;
}

//check of correctness of format of input file. it must be CSV.

int correctness(char* input, int size){
    int i, r = 0;
    for (i = 0; i < size; i++){
	if (input[i] == ','){
	    if ((r == 0) && (i != 0)){
		r = 1;
	    }
	    else{
		return -1;
	    }
	}
	else{
	    if (input[i] == '-'){
		if ((i != 0) && (r != 1)){
		    return -1;
		}
		else{
		    r = 2;
		}
	    }
	    else{
		if ((input[i] <= '9') && (input[i] >= '0')){
		    r = 0;	  
		}
		else{
		    return -1;
		}
	    }
	}
    }
    if (r!=0){
	return -1;
    }
  
  //number can't begin with 0
  
    if (size > 1){
	if ((input[0] == '0') && (input[1] <= '9') && (input[1] >= '0')){
	    return -2;
	} 
    }
    if (size > 2){
	for (i = 0; i < size-2; i++){
	    if ((input[i] == ',') && (input[i+1] == '0') && (input[i+2] <= '9') && (input[i+2] >= '0')){
		return -2;
	    }
	}
    }
    return 0;
}

void LOG_PRINT_ERROR(char* error_text){
    LOG_PRINT(ERROR, error_text);
    perror(error_text);
    exit(EXIT_FAILURE);
}	

int find_comma(FILE *fd){
    fseek(fd, 0, SEEK_CUR);
    int delta = 0;
    char c[2];
    fgets(c, 2, fd);
    printf("c=%s\n", c);
    while (c[0] != ','){
      fseek(fd, -2, SEEK_CUR);
      fgets(c, 2, fd);
      delta++;
    }
    return delta;  
}

//splitting input file into chunks which are mapped and parsed on arguments for sorting separately. return double pointer on numbers, which will be sorted.

int** parsed_arg(char *INPUT){
    FILE *fd;
    fd = fopen(INPUT, "r");
//    int fd_int = fileno(fd);
    int fd_int;
    LOG_PRINT(INFO,"the input file was opened for reading");
    off_t size = size_of_file(INPUT);
    printf("size_of_file=%lld\n", (long long int) size);
    int part = max_size_of_int + 12;
    printf("part=%d\n", part);
    int num_of_parts = size/max_size_of_int + 1;
    printf("num_of_parts=%d\n", num_of_parts);
    int i, k, chunk, start = 0, correctness_int, end;
    int **M;
    char *map_input;
    char map_input_array[part];
    int num_of_args;
    char *arg[part+1];
    FILE *fd_tmp;
    char *tmp;
    int fd_tmp_int;
    int delta;
    
    M = malloc(num_of_parts*sizeof(int*));
    
    for (i = 0; i < num_of_parts; i++){
	fseek(fd, start, SEEK_SET);
	chunk = part - 1;
//	printf("%c\n", fgetc(fd));
	if ((size - start + 1) <= part){
	    printf("(size - start + 1) <= part\n");
	    chunk = size - start;
	}
	else{
	    printf("(size - start + 1) > part\n");
	    end = start + part - 1;
	    printf("end=%d\n", end);
	    fseek(fd, end, SEEK_SET);	 	    
/*	    while(fgetc(fd) != ','){
		printf("in while\n");
		end = end - 2;
		fseek(fd, end, SEEK_SET);
		chunk--;		
	    }*/
	    delta = find_comma(fd);
	    printf("delta=%d\n", delta);
	    chunk = chunk - delta;

	    if (chunk < max_size_of_int){
		LOG_PRINT_ERROR("illegal size of number in the input file");
	    }
	}
	printf("chunk=%d\n", chunk);
	
	fseek(fd, start, SEEK_SET);
	fd_tmp = fopen("tmp", "w");
	tmp = malloc((chunk+1)*sizeof(char));
	fgets(tmp, chunk+1, fd);
	printf("tmp=%s\n", tmp);	
	fprintf(fd_tmp, "%s", tmp);
	free(tmp);
	fclose(fd_tmp);
	fd_tmp_int = open("tmp", O_RDONLY);		
	map_input = mmap(0, chunk, PROT_READ, MAP_SHARED, fd_tmp_int, 0);
	if (map_input == MAP_FAILED){
	    close(fd_tmp_int);
	    LOG_PRINT_ERROR("mapping of the input file failed");
	}  
	LOG_PRINT(INFO,"the input file was mapped");
	printf("map_input=%s\n", map_input);
//    	LOG_PRINT("INFO: the content of the input file: %s", map_input);
	correctness_int = correctness(map_input, chunk);
	if (correctness_int == -1){
	    fclose(fd);
	    LOG_PRINT_ERROR("the input file isn't in CSV format");
	}
	if (correctness_int == -2){
	    fclose(fd);
	    LOG_PRINT_ERROR("number with more than one digit can't begin with 0.");
	}  
	LOG_PRINT(INFO,"the content of the input file is correct");    
	num_of_args = 1; //quantity of numbers in input
	for (k = 0; k < chunk; k++){
	    map_input_array[k] = map_input[k];
	    if (map_input[k] == ','){
		num_of_args++;
	    }
	}
	printf("num_of_args=%d\n", num_of_args);
	if (num_of_args >= INT_MAX){  //impossibly
	    fclose(fd);
	    LOG_PRINT_ERROR("quantity of numbers in input file is very big");
	}
	LOG_PRINT(INFO,"quantity of numbers in input file is acceptable");
	if (munmap(map_input, chunk) == -1){
	    fclose(fd);//
	    LOG_PRINT_ERROR("unmapping of the input file failed");
	}  
	LOG_PRINT(INFO,"the input file was unmapped");
	arg[0] = strtok(map_input_array, ",");
	printf("arg[0]=%s\n", arg[0]);
	k = 1;
	while (arg[k-1] != NULL){
	    arg[k] = strtok(NULL, ",");
//	    printf("arg[%d]=%s\n", k, arg[k]);
	    k++;
	}
	LOG_PRINT(INFO,"the content of the input file was parsed for sorting");
	M[i] = malloc((num_of_args+1) * sizeof(int));
	for (k = 0; k < num_of_args; k++){
	    M[i][k+1] = strtol(arg[k], NULL, 10);
	    strcpy(arg[k],"");
	    printf("M[%d][%d]=%d\n", i, k+1, M[i][k+1]);
	    if ((M[i][k+1] >= INT_MAX) || (M[i][k+1] <= INT_MIN)){
		fclose(fd);
		free(M[i]);
		LOG_PRINT_ERROR("illegal size of number in the input file");
	    }
	}
	LOG_PRINT(INFO,"sizes of numbers in the input file are acceptable");
	M[i][0] = num_of_args;
	if ((size - start + 1) <= part){
	    break;
	}
	start = start + chunk + 1;
	printf("start=%d\n", start);
    }
    remove("tmp");
    fclose(fd);
    exact_num_of_parts = i + 1;
    printf("exact_num_of_parts=%d\n", exact_num_of_parts);
    return M;  
}


int* merge_sorted_arrays(int **M){
    int i, t, k, l, p, black_index, min_index;
    int *output;
    int black[exact_num_of_parts];
    int counter[exact_num_of_parts];
    for (i = 0; i < exact_num_of_parts; i++){
	counter[i] = 0;
    } 
    int min = M[0][1];
    min_index = 0;
    int r = 0;
    int exact_num_of_args = 0;
    for (i = 0; i < exact_num_of_parts; i++){
	exact_num_of_args = exact_num_of_args + M[i][0];
    } 
    output = malloc(exact_num_of_args*sizeof(int));
    for (k = 0; k < exact_num_of_args; k++){ 
	for(i = 0; i < exact_num_of_parts; i++){
	    black_index = 0;
	    for(t = 0; t < r; t++){
		if (black[t] == i){
		    black_index = 1;
		    break;
		}
	    }
	    if (black_index == 1){  //if in black list
		continue;
	    }
	    if (M[i][1] <= min){  //else
		min = M[i][1];
		min_index = i;
	    }
	}
	output[k] = min;
//	printf("output[%d]=%d\n", k, output[k]);
	counter[min_index]++;
	if ((counter[min_index] + 1) <= M[min_index][0]){
	    M[min_index][1] = M[min_index][1+counter[min_index]];
	}
	else{
	    black[r] = min_index;
	    r++;
	}
	if (r == exact_num_of_parts){
	    break;
	}	    
	for(l = 0; l < exact_num_of_parts; l++){
	    p = 0;
	    for(t = 0; t < r; t++){
		if (black[t] == l){   //if l is in black list
		    p = 1;
		    break;
		}		    
	    }
	    if (p == 0){
		min = M[l][1];
		break;
	    }
	}
    }
    return output;
}


void writing(int *M, int num_of_args, char *OUTPUT, char *INPUT){    //not used now
    char *map_output;
    int size = size_of_file(INPUT);
    int fd = open(OUTPUT, O_RDWR | O_CREAT | O_TRUNC, (mode_t)0600);
    if (fd == -1){
	LOG_PRINT_ERROR("opening of the output file for writing failed");
    }  
    LOG_PRINT(INFO,"the output file  was opened for writing");
    int end = lseek(fd, size-1, SEEK_SET);  
    if (end == -1){
	close(fd);
	LOG_PRINT_ERROR("stretching the output file failed");
    }  
    LOG_PRINT(INFO,"the output file was stretched");
    end = write(fd, "", 1); //stretching of output file  
    if (end != 1){
	close(fd);
	LOG_PRINT_ERROR("writing the last byte to the output file failed");
    }
    LOG_PRINT(INFO,"the last byte was written to the output file");
    map_output = mmap(0, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);  
    if (map_output == MAP_FAILED){
	close(fd);
	LOG_PRINT_ERROR("mapping the output file failed");
    } 
    LOG_PRINT(INFO,"the output file was mapped");
    char str[6]; 
    int i;
    for (i = 1; i < num_of_args+1; i++){
	snprintf(str, 6 , "%d", M[i]);	
	strcat(map_output, str);
	if (i != num_of_args){
	    strcat(map_output, ",");
	}  
    }
    LOG_PRINT(INFO,"writing in the output file was completed");
//    printf("%s\n", map_output);
//    LOG_PRINT("INFO: the content of the output file: %s", map_output);
    if (munmap(map_output, size) == -1){
	close(fd);
	LOG_PRINT_ERROR("unmapping the output file failed");
    }
    LOG_PRINT(INFO,"the output file was unmapped");
    close(fd);
}
  
  
void helpYourself(int *m, int left, int right, int mid) {
    int i=0, j=0;
    int l = mid-left;
    int *ml = m+left, *mr = m+mid;
    int r = right-mid;
    int *s = malloc((l+r)*sizeof(int));
    while ((i<l)&&(j<r)) {
	s[i+j] = (ml[i]<mr[j])?ml[i++]:mr[j++];
    }
    while (i<l) {
	s[i+j] = ml[i++];
    }
    while (j<r) {
	s[i+j] = mr[j++];
    }
    memcpy(m+left, s, (right-left)*sizeof(int));
    free(s);
}

void myMysteriousSort(int *m, int left, int right) {
    if ((right-left) < 2) {
	return;
    }
    int mid = (right+left)/2;
    myMysteriousSort(m, left, mid);
    myMysteriousSort(m, mid, right);
    helpYourself(m, left, right, mid);
}

int main(int argc, char **argv){
    SET_ERROR_LEVEL(ERROR);
    char INPUT[50], OUTPUT[50];
    if ((argc == 2) && (strcmp(argv[1],"-h")) == 0){
	printf("\nHELP\n\nThe first command line argument is path of input file, the second - output file.\nFormat of input file is CSV.\nAll numbers in input file and their quantity must be integer\n\n");
	return 0;
    }
    else{  
	if (argc != 3){
	    printf("Call of help with command line argument '-h'\n");
	    return 0; 
	}
	else{
	    strcpy(INPUT, argv[1]);
	    strcpy(OUTPUT, argv[2]);
	}
    }
    int **M = parsed_arg(INPUT);
    int i, k, exact_num_of_args = 0;
    for (i = 0; i < exact_num_of_parts; i++){
	exact_num_of_args = exact_num_of_args + M[i][0];
    } 
    
    printf("exact_num_of_args=%d\n", exact_num_of_args);

    for (i = 0; i < exact_num_of_parts; i++){
	myMysteriousSort(M[i], 1, M[i][0]+1);
	printf("%d: ", i);
	for (k = 1; k < M[i][0]+1; k++){
	    printf("%d ", M[i][k]);
	} 
	printf("\n");
    }

    int *output = merge_sorted_arrays(M);
    
    for (i = 0; i < exact_num_of_args; i++){
	printf("%d ", output[i]);
    }
    
    free(output);
    
    for (i = 0; i < exact_num_of_parts; i++){  
	free(M[i]); 
    }
    free(M);
    
    LOG_PRINT(INFO,"sorting completed");
//    writing(M[i], num_of_args, OUTPUT, INPUT);
    
    LOG_PRINT(INFO,"the program successfully completed");
    return 0;
}